Міністерство освіти і науки
Національний університет «Львівська політехніка»
Кафедра ЕОМ
Звіт
до лабораторної роботи № 2
з дисципліни: “Алгоритми та методи обчислень”
на тему: “ Розробка та дослідження ефективності
методів пошуку даних ”
Варіанти – 15, 2, 1
Львів – 2016
Мета роботи
• Дослідити ефективність методів пошуку на прикладі різних методів організації хеш-таблиць. Вивчити основні методи побудови хеш-таблиць, дослідити переваги і недоліки, властиві різним методам, оцінити ефективність і провести порівняння ефективностей.
Загальне завдання:
Написати програму, що отримує на вході послідовність слів (ключів), будує дві хеш-таблиці цих слів, виконує операції додавання нових слів в побудовані хеш-таблиці та вилучення заданих елементів з таблиць, виводить на екран вміст кожної таблиці, здійснює багаторазовий пошук довільних слів в цих хеш-таблицях, порівнює ефективності різних методів організації хеш-таблиць.
Список вхідних слів довжиною n=28 задати у вигляді текстового файла data.txt . Файл data.txt має містити таку інформацію (всі слова (або числа) записуються латинськими літерами підряд через кому):
прізвище, ім'я, побатькові,
день, місяць,рік народження,
назва компанii мобільного зв'язку,
підряд через пробіл всі цифри мобільного телефона, починаючи з кода оператора (всього 10 цифр),
назва області, міста і вулиці в адресі прописки,
номер будинку і квартири в адресі прописки,
абревіатура інститута, кафедри, групи,
день, місяць,рік виконання лабораторної роботи.
Наприклад: Вміст файлу data.txt :
Petrenko,Bogdan,Sergyjovuch,25,3,1989,Kyivstar,0,6,7,5,7,6,4,9,2,1,Lvivska,Lviv,Bandery,12,1,IKTA,EOM,KI-21,12,4,2010
Весь вхідний список слів розмістити в першій хеш-таблиці розмірністю m=37, метод побудови якої вибрати згідно з варіантом. Також весь вхідний список слів розмістити у другій хеш-таблиці, метод побудови якої вибрати самостійно. Забороняється вибирати хеш-функції, що співпадають з прикладами хеш-функції, наведених в цих методичних вказівках. При виборі хеш-функції намагатись, щоб ефективність організації другої таблиці була вищою, ніж першої.
Забезпечити виконання програмою на вимогу користувача операцій додавання та вилучення елементів з хеш-таблиць.
В процесі роботи з таблицями на вимогу користувача програма повинна виводити на екран вміст кожної хеш-таблиці.
Під час пошуку слів в хеш-таблицях програма повинна виводити на екран послідовність слів з якими виконуються порівняння і кількість виконаних операцій порівняння.
Особисте завдання:
Завдання 1:
а) Побудувати хеш-таблицю розмірністю m=37, метод організації якої:
h(key) = [(АSCII-код останього символа ключа) *(кількість символів в ключі)] % m;
б) Розв'язання колізій при хешуванні здійснити:
методом відкритої адресації з функцією повторного хешування
hі(key) = ( h(key) + i ) % m;
Завдання 2:
Побудувати хеш-таблицю. Розмірність таблиці (m), вигляд хеш-функції h(key) та вигляд функції повторного хешування hi(key) вибрати самостійно, керуючись умовами покращення ефективності методу побудови хеш-таблиці.
Розв'язання колізій при хешуванні здійснити методом роздільних ланцюжків.
Текст програми:
#include <iostream>
#include <fstream>
#include <string>
#define M 37
#define N 7
using namespace std;
//функції для першої таблиці
int Func_Key(string str) //обчислення хеш-функції
{
//h(key) = [(АSCII-код останього символа ключа) *(кількість символів в ключі)] % m;
return (str[size(str) - 1] * size(str)) % M;
}
int m = 1;
int Func_doubleKey(string** table, string str, int vubir = 0) //обчислення повторних хеш-функцій для розвязання колізій
{
int Key = Func_Key(str);
int doubleKey;
int i = 1;
do
{
doubleKey = (Key + i++) % M;
if ((table[doubleKey] == NULL))
return doubleKey;
if ((*table[doubleKey] != str) && vubir == 3)
{
cout << *table[doubleKey] << ", ";
m++;
}
} while ((*table[doubleKey] != str)); //цикл виконуватиметься до...
